#include "skiplist.h"
using namespace std;

template <class T>
void SkipList<T>::insert(T v)
{
	Node* dw = insert(root, v);
	while(dw) // keep flipping
	{
		Node* tmp = root,* nw = new Node(v); 
		
		root = new Node();
		root->dw = tmp;
		root->nx = nw;
		
		nw->dw = dw;
		
		dw = (rand()%2)? nw: NULL;   
	}
}

template <class T>
bool SkipList<T>::search(T v)
{
	return search(root, v);  
}

template <class T>
void SkipList<T>::clear()
{
	remove_all();
	root = new Node();
}

template <class T>
void SkipList<T>::erase(T v)
{
	erase(root, v);
	while(root->nx == NULL && root->dw)
	{
		Node* tmp = root->dw;
		delete root;
		root = tmp;
	}
}

template <class T>
void SkipList<T>::print()
{
	cout << '\n';	
	for(Node* i = root; i; i = i->dw)
	{
		for(Node* j = i; j; j = j->nx)
			cout << setw(4) << j->data;
		cout << '\n';
	}
	cout << '\n';	
}

template <class T>
int SkipList<T>::height()
{
	int ans = 0;
	for(Node* i = root; i; i = i->dw) ++ans;
	return ans;

}

template <class T>
int SkipList<T>::count_nodes()
{
	int ans = 0;
	for(Node* i = root; i; i = i->dw)
		for(Node* j = i; j; j = j->nx)
			++ans;
	return ans;
}

template <class T>
typename SkipList<T>::Node* SkipList<T>::insert(Node* b, T v)
{
	if(b == NULL) return NULL;

	while(b->nx && v > b->nx->data )
		b = b->nx;
	
	if(b->nx && b->nx->data == v) // exists
		return NULL;
	
	Node* dw = insert(b->dw, v);
	
	if(b->dw != NULL && !dw) return NULL;

	// inserts	
	Node* tmp = b->nx;
	b->nx = new Node(v);
	b->nx->nx = tmp;
	b->nx->dw = dw; 
		
	return (rand()%2)? b->nx: NULL;
}

template <class T>
bool SkipList<T>::search(Node* b, T v)
{
	if(b == NULL) return 0;

	while(b->nx && v > b->nx->data )
		b = b->nx;
	
	if(b->nx && b->nx->data == v) // exists
		return 1;

	return search(b->dw, v);
}

template <class T>
void SkipList<T>::erase(Node* b, T v)
{
	if(b == NULL) return ;

	while(b->nx && v > b->nx->data )
		b = b->nx;
	
	erase(b->dw, v);
		
	if(b->nx && b->nx->data == v) // removes 
	{
		Node* tmp = b->nx->nx;
		delete b->nx;
		b->nx = tmp;
	}
}

template <class T>
void SkipList<T>::remove_all()
{			 
	Node* i = root, *j, *t;

	while(i)
	{
		j = i; i = i->dw;
		while(j->nx)
		{
			t = j->nx;
			delete j;
			j = t;
		}
		delete j;
	}
}
